package org.example.myleet.rosalind.pcov;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    public static void main(String[] args) throws IOException {
        Solution solution = new Solution();
        String path = solution.getClass().getResource("").getPath() + "example.txt";
        try (BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(path)))) {
            List<String> reads = new ArrayList<>();
            String line;
            while (null != (line = br.readLine())) {
                line = line.trim();
                if (1 > line.length()) {
                    break;
                }
                reads.add(line);
            }
            /**
             * https://zhuanlan.zhihu.com/p/54466660
             * 简化版的De Bruijn Graph（DBG）法进行序列拼接
             * 1、将read（k-mer）的[0,k-2]长度的部分作为前缀，将[1,k-1]长度部分作为后缀
             * 2、将前缀与后缀相同的节点连接成有向边，形成DBG，由于题目给出的限定是环状DNA且DBG是无分叉的，因此这里DBG节点的next都是单个的
             * 3、从head节点开始一直next，连接每个节点的最后一个字符就是结果序列，由于是环状DNA，因此从任意一个节点开始遍历都可以
             */
            Map<String, DbgNode> prefixMapDbgNode = new HashMap<>(reads.size());
            for (String read : reads) {
                DbgNode node = new DbgNode(read);
                if (prefixMapDbgNode.containsKey(node.prefix)) {
                    System.out.printf("conflict: %s, %s\n", prefixMapDbgNode.get(node.prefix), read);
                    return;
                }
                prefixMapDbgNode.put(node.prefix, node);
            }
            DbgNode head = prefixMapDbgNode.remove(reads.get(0).substring(1));
            DbgNode cur = head;
            while (!prefixMapDbgNode.isEmpty()) {
                DbgNode next = prefixMapDbgNode.remove(cur.suffix);
                if (null == next) {
                    System.out.println("can not find next read");
                    return;
                }
                cur.next = next;
                cur = next;
            }
            StringBuilder res = new StringBuilder();
            res.append(head.lastChar);
            cur = head.next;
            while (null != cur && cur != head) {
                res.append(cur.lastChar);
                cur = cur.next;
            }
            System.out.println(res);
        }
    }

    static class DbgNode {
        String read;
        String prefix;
        String suffix;
        char lastChar;
        DbgNode next;

        public DbgNode(String read) {
            this.read = read;
            lastChar = read.charAt(read.length() - 1);
            prefix = read.substring(0, read.length() - 1);
            suffix = read.substring(1);
        }
    }
}
